WannaflyCamp day6

补题进度：2/11
tls组合数学选讲
中山左老师训练题

---

组合数学选讲

---

A

题意

题解

---

B

题意

题解

---

C

题意

题解

---

D

题意

题解

---

E

题意

题解

---

F

题意

定义一颗二叉树的
高度差：二叉树所有节点左右儿子高度差的最大值
不平衡度：这棵树的所有节点左右子树节点数之差的最大值
问所有高度为n的二叉树中，高度差不超过d的树不平衡度的最大值

题解

高度为$n$的树的高度差最大为$d$
不平衡度的最大值一定是：一颗高度为$n-1$的满二叉树，和一颗高度为$n-1$最大不平衡二叉树，之差。
高度为n-1的满二叉树的节点数为$2^{n-1}-1$
高度为$n-1$的最大不平衡二叉树的节点数为$f(n)$
$$f(n)=1+f(n-1)+f(n-d-1) (n>d)$$
$$f(n)=n (n<=d)$$

---

G

题意

题解

---

H

题意

$n$ 张卡片，其中 $m$ 张是特殊卡片，每次可以去一张牌。问取出的至少有 $k$ 张特殊卡片的期望次数(特殊卡不放回)

题解

• 显然满足几何分布
• 这里的至少k张实际上就是恰好k张
• $\sum_{i=0}^{k-1} \frac {n-i}{m-i}$

---

I

题意

题解

---

J

题意

题解

---

K

题意

题解

---